package com.husk.leetcode.tree;

import org.junit.Test;

/**
 * <p>
 * 腾讯面试题
 * </p>
 *
 * @author hushunke@sm.vvip-u.com
 * @since 2021/3/22
 */
public class TencentTree {

    /**
     * 找二叉树的公共祖先
     *
     * @param nums 二叉树
     * @param p
     * @param q
     * @return
     */
    public int tree(Integer[] nums, Integer p, Integer q) {
        Integer pIndex = null, qIndex = null;

        for (int i = 0; i < nums.length; i++) {
            if (pIndex == null && p.equals(nums[i])) {
                pIndex = i;
            } else if (qIndex == null && q.equals(nums[i])) {
                qIndex = i;
            } else if (pIndex != null && qIndex != null) {
                break;
            }
        }
        if (pIndex == null || qIndex == null) {
            return -1;
        }
        if (pIndex == 0 || qIndex == 0) {
            return nums[0];
        }

        // 数字          数组下标
        // root: n,     index = i+1
        // left: 2n,    index = 2i+1
        // right: 2n+1, index = 2i+2

        // 算到树相等为止
        while (!pIndex.equals(qIndex)) {
            if (pIndex > qIndex) {
                pIndex = calcParent(pIndex);
            } else {
                qIndex = calcParent(qIndex);
            }
        }
        return nums[pIndex];
    }

    public int calcParent(int index) {
        if (index % 2 == 0) {
            // 能够被2整除, 右树
            return Math.max((index - 2) / 2, 0);
        } else {
            // 左树
            return Math.max((index - 1) / 2, 0);
        }
    }

    @Test
    public void test() {
        Integer[] nums = new Integer[]{3, 5, 1, 6, 2, 0, 8, null, null, 7, 4};
        int p = 6, q = 4;
        Integer result = this.tree(nums, p, q);
        System.out.println(result);
    }

    @Test
    public void test2() {
        Integer[] nums = new Integer[]{3, 5, 1, 6, 2, 0, 8, null, null, 7, 4};
        int p = 5, q = 4;
        Integer result = this.tree(nums, p, q);
        System.out.println(result);

    }

}
